#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
using namespace std;

void _merge_sort(vector<int>& arr, vector<int>& tmp, int left, int right)
{
	if (left >= right) return;

	int mid = (right + left) / 2;
	//[left, mid] [mid + 1, right] ;

	_merge_sort(arr, tmp, left, mid);
	_merge_sort(arr, tmp, mid + 1, right);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2]) tmp[i++] = arr[begin1++];
		else tmp[i++] = arr[begin2++];
	}
	while(begin1 <= end1) tmp[i++] = arr[begin1++];
	while(begin2 <= end2) tmp[i++] = arr[begin2++];

	for (int j = left; j <= right; j++) arr[j] = tmp[j];
}

void merge_sort(vector<int>& arr, int n)
{
	vector<int> tmp(n);
	_merge_sort(arr, tmp, 0, n - 1);
}

int main()
{
	vector<int> arr = { 5,9,46,8,16,43,7,2,3,1 };
	int n = arr.size();
	merge_sort(arr, n);
	for (auto e : arr)
		cout << e << " ";
	cout << endl;
}